package offer;

import java.util.ArrayList;
import java.util.List;

public class offer_0100 {
    public int minimumTotal(List<List<Integer>> triangle) {

        int len=triangle.size();
        int[] list=new int[len+1];
        int[] min=new int[1];
        min[0]=2147483647;
        forward(triangle,0,0,len,list,min);
        return min[0];
    }
    public void forward(List<List<Integer>> triangle,int i,int j,int len,int[] list,int[] min){
        if(i==len){
            int tem=0;
            for(int k=0;k<len;++k){
                tem+=triangle.get(k).get(list[k]);
            }
            min[0]=(min[0]<tem)?min[0]:tem;
            return;
        }
        list[i+1]=j;
        forward(triangle,i+1,j,len,list,min);
        list[i+1]=j+1;
        forward(triangle,i+1,j+1,len,list,min);
    }
}
